import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * Created by L.jp
 * Description:给定一个无重复元素的正整数数组candidates和一个正整数target，找出candidates中所有可以使数字和为目标数target的唯一组合。
 * candidates中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
 * 对于给定的输入，保证和为target 的唯一组合数少于 150 个
 *
 * User: 86189
 * Date: 2021-11-26
 * Time: 23:40
 */
public class CombinedSum {
    public static void dfs(List<List<Integer>> list,List<Integer> tmpList,int [] candidates,int target,int sum,int curIndex){
        // 找到了数字和为 target 的组合
        if (sum == target) {
            list.add(new ArrayList<>(tmpList));
            return;
        }
        //i不是一直从0开始，而是从当前位置开始，因为可以重复选择那个元素，所以tmpList.add(candidates[i]),sum+candidates[i],curIndex==i;
        for (int i = curIndex; i < candidates.length; i++) {//每次递归的i都是从上一次的当前位置开始
            if (sum + candidates[i] > target) break;// 如果 上一次的sum +这一次的 candidates[i] > target 就可以直接终止遍历，不用再看下面的情况了
            tmpList.add(candidates[i]);
            dfs(list, tmpList, candidates, target, sum + candidates[i], i);
            tmpList.remove(tmpList.size() - 1); // 回溯，移除路径 path 最后一个元素
        }
    }
    public static  List<List<Integer>> combinationSum(int[] candidates, int target){
        List<List<Integer>> list = new ArrayList<>();//存储最终结果
        List<Integer> tmpList=new ArrayList<>();//存储临时结果
        if(candidates.length==0){
            return list;
        }
        Arrays.sort(candidates); // 先进行排序
        dfs(list, tmpList, candidates, target, 0, 0);//开始查找符合条件的结果
        return list;//最终递归结束返回结果
    }
    public static void main(String[] args) {
        int[] candidates={2,3,6,7};
        int target=7;
        List<List<Integer>> list=combinationSum(candidates,target);
        System.out.println(list);

    }
}
